//给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。 
//
// 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满
//足条件的子矩阵，返回任意一个均可。 
//
// 注意：本题相对书上原题稍作改动 
//
// 示例: 
//
// 输入:
//[
//   [-1,0],
//   [0,-1]
//]
//输出: [0,1,0,1]
//解释: 输入中标粗的元素即为输出所表示的矩阵 
//
// 说明： 
//
// 
// 1 <= matrix.length, matrix[0].length <= 200 
// 
// Related Topics 动态规划 
// 👍 19 👎 0

  
package com.yun.leetcode.editor.cn;

import java.util.Stack;

public class MaxSubmatrixLcci {
    public static void main(String[] args) {
        Solution solution = new MaxSubmatrixLcci().new Solution();
    }
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        // 求最大子矩阵
        int maxArea = 0;
        // 先求出直方图
        int[] height = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                height[j] = matrix[i][j] == 0 ? 0 : height[j] + 1;
            }
            maxArea = Math.max(maxRevFromBottom(height), maxArea);
        }

        // 这个要记录最大矩阵，
        // 还需要有一个临时数组，当最大矩阵更新时，去更新数组

        return null;
    }

    private int maxRevFromBottom(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        // 获取直方图了
        // 需要用一个栈来存储，向左扩充，向右扩充。当前柱体的最大值。
        // 栈大于当前的数，就一直往里放；
        // 小于等于前一个数，就往回扩；此时可以确定好，这个回扩位置为高，宽到弹出位置的矩形。获取它和临时变量maxArea的最大值。
        // 直到栈顶存储index位置的元素大于当前元素。
        // 如果弹出当前元素后，栈空了，则代表这个矩形从-1位置到当前index位置
        //
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - k - 1) * height[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (height.length - k - 1) * height[j]; // 这里没有 i 取值
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}